'''
快速排序是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，
其中一部分的所有数据都比另外一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，
以此达到整个数据变成有序序列。
算法步骤：
选择基准值：从数列中挑出一个元素，称为“基准”（pivot），
分区操作：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归排序子序列：递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
时间复杂度分析：
最好情况：每次分区操作都能将数组分成两个等大的部分，此时时间复杂度为O(nlogn)。
最坏情况：当输入数组已经是有序或逆序时，每次分区操作只能将数组分成一个元素和一个剩余元素的子数组，此时时间复杂度退化为O(n^2 )。
平均情况：时间复杂度为O(nlogn)。
空间复杂度分析：
快速排序是递归的，需要额外的栈空间来保存递归调用。在最坏情况下（即每次分区操作都极不平衡），空间复杂度为O(n)，因为递归调用的深度可能达到n。
在平均情况下，空间复杂度通常是O(logn)，但需要注意的是，这是递归栈的深度，而实际的空间复杂度（包括递归栈和额外的临时空间）可能会更高。
快速排序是一种原地排序算法（in-place sort），除了递归调用栈之外，它只需要常数量级的额外空间。
优点：
平均情况下时间复杂度较低，为O(nlogn)。
可以原地排序，空间复杂度较低（不考虑递归栈空间）。
缺点：
最坏情况下的时间复杂度较高，为O(n^2 )。
递归深度较大时，可能会占用较多的栈空间。
实际应用：
快速排序不属于稳定性排序，在实际应用中非常广泛，特别是在处理大数据集时。由于其平均情况下的高效性，它经常被用作各种排序算法和数据结构（如优先队列）的底层实现。
然而，在处理小数据集或基本有序的数据集时，可能需要考虑其他排序算法（如插入排序或归并排序）以获得更好的性能。
'''
import random
class Solution:
    def quick_sort(self, arr):
        n = len(arr)
        if n <= 1:
            return arr
        pivot = arr[-1]
        low_lst = []
        mid_lst = []
        high_lst = []
        for num in arr:
            if num < pivot:
                low_lst.append(num)
            elif num == pivot:      #注意等于基准元素要归于中间列表，不能归左右列表
                mid_lst.append(num)
            else:
                high_lst.append(num)
        return self.quick_sort(low_lst) +mid_lst +self.quick_sort(high_lst)
#示例
if __name__ == '__main__':
    arr = random.sample(range(100), 10)
    print(arr)
    print(Solution().quick_sort(arr))

